1 /** 2 * Templates for hashing types. 3 * Copyright: © 2015 Economic Modeling Specialists, Intl. 4 * Authors: Brian Schott 5 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 6 */ 7 module containers.internal.hash; 8 9 static if (hash_t.sizeof == 4) 10 { 11 hash_t generateHash(T)(const T value) 12 { 13 return hashOf(value); 14 } 15 } 16 else 17 { 18 hash_t generateHash(T)(const T value) if (!is(T == string)) 19 { 20 return hashOf(value); 21 } 22 23 /** 24 * A variant of the FNV-1a (64) hashing algorithm. 25 */ 26 hash_t generateHash(T)(T value) pure nothrow @nogc @trusted if (is(T == string)) 27 { 28 hash_t h = 0xcbf29ce484222325; 29 foreach (const ubyte c; cast(ubyte[]) value) 30 { 31 h ^= ((c - ' ') * 13); 32 h *= 0x100000001b3; 33 } 34 return h; 35 } 36 } 37 38 /** 39 * Convert a hash code into a valid array index. 40 * 41 * Prams: 42 * hash = the hash code to be mapped 43 * len = the length of the array that backs the hash container. 44 */ 45 size_t hashToIndex(const size_t hash, const size_t len) pure nothrow @nogc @safe 46 { 47 // This magic number taken from 48 // https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ 49 // 50 // It's amazing how much faster this makes the hash data structures 51 // when faced with low quality hash functions. 52 static if (size_t.sizeof == 8) 53 enum ulong magic = 11_400_714_819_323_198_485UL; 54 else 55 enum uint magic = 2_654_435_769U; 56 57 if (len <= 1) 58 return 0; 59 version(LDC) 60 { 61 import ldc.intrinsics : llvm_cttz; 62 return (hash * magic) >>> ((size_t.sizeof * 8) - llvm_cttz(len, true)); 63 } 64 else 65 { 66 import core.bitop : bsf; 67 return (hash * magic) >>> ((size_t.sizeof * 8) - bsf(len)); 68 } 69 } 70 71 enum size_t DEFAULT_BUCKET_COUNT = 8;